package xyz.scootaloo.oj.leetcode

import cn.hutool.core.lang.Console
import org.junit.Test
import xyz.scootaloo.oj.ds.TreeNode

/**
 * @author flutterdash@qq.com
 * @since 2021/4/30 9:31
 */
class P105 {

    fun buildTree(preorder: IntArray, inorder: IntArray): TreeNode? {
        val size = preorder.size
        if (size == 0)
            return null

        val indexMap = HashMap<Int, Int>()
        for (index in inorder.indices)
            indexMap[inorder[index]] = index

        // 分组
        fun grouping(preLeft: Int, preRight: Int, inLeft: Int, inRight: Int): TreeNode? {
            if (preLeft > preRight)
                return null
            val rootValue = preorder[preLeft]
            val root = TreeNode(rootValue)
            if (preRight - preLeft == 0)
                return root

            val pos = indexMap[rootValue]
            if (pos != null) {
                val leftSubTreeNodeCount = pos - inLeft
                root.left = grouping(
                    preLeft + 1, preLeft + leftSubTreeNodeCount,
                    inLeft, pos - 1
                )
                root.right = grouping(
                    preLeft + leftSubTreeNodeCount + 1, preRight,
                    pos + 1, inRight
                )
            }

            return root
        }

        return grouping(0, size - 1, 0, size - 1)
    }

    @Test
    fun test0() {
        val preorder = intArrayOf(3, 9, 20, 15, 7)
        val inorder = intArrayOf(9, 3, 15, 20, 7)
        val root = buildTree(preorder, inorder)
        Console.log(root)
    }

    @Test
    fun test1() {
        val preorder = intArrayOf(1, 2)
        val inorder = intArrayOf(2, 1)
        val root = buildTree(preorder, inorder)
        Console.log(root)
    }

}
